Corelab Seminar
2014-2015
Stratis Ioannidis (Technicolor research center in Los Altos, CA)
Linear Regression as a Non-Cooperative Game
Abstract.
The statistical analysis of personal data is a cornerstone of
several experimental sciences, such as medicine and sociology, and has
recently become a commonplace-yet controversial-aspect of the Internet
economy. The monetary and societal benefits of statistical estimation over
personal data are often off-set by a privacy cost incurred by participating
individuals. We propose a game-theoretic model to express this trade-off
in the context of linear regression, a ubiquitous statistical task. In particular,
we consider an analyst wishing to learn a linear model over responses solicited
from several individuals. Though individuals benefit from correct estimation of
the model, they also incur a privacy cost when revealing their responses.
To address this, individuals strategically add noise to their responses, to minimize
a cost that captures both how well the model is estimated, as well as the privacy
violation they incur. We study the Nash equilibria of the resulting non-cooperative
game, establishing the existence of a unique equilibrium for which costs are finite.
We also determine the price of stability for several classes of privacy and estimation costs.
Finally, we prove that estimating the linear model through
a generalized least-squares minimization is optimal
among all linear unbiased estimators: this result extends the famous Aitken/Gauss-Markov
theorem in statistics, indicating that its conclusion persists even when individuals add noise strategically.
This is joint work with Patrick Loiseau and Michela Chessa from Eurecom, France.